We give precise quantum resource estimates for Shor's algorithm to computediscrete logarithms on elliptic curves over prime fields. The estimates arederived from a simulation of a Toffoli gate network for controlled ellipticcurve point addition, implemented within the framework of the quantum computingsoftware tool suite LIQ$Ui|\rangle$. We determine circuit implementations forreversible modular arithmetic, including modular addition, multiplication andinversion, as well as reversible elliptic curve point addition. We concludethat elliptic curve discrete logarithms on an elliptic curve defined over an$n$-bit prime field can be computed on a quantum computer with at most $9n +2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3\log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate theToffoli networks corresponding to the controlled elliptic curve point additionas the core piece of Shor's algorithm for the NIST standard curves P-192,P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons torecent resource estimates for Shor's factoring algorithm. The results alsosupport estimates given earlier by Proos and Zalka and indicate that, forcurrent parameters at comparable classical security levels, the number ofqubits required to tackle elliptic curves is less than for attacking RSA,suggesting that indeed ECC is an easier target than RSA.
展开▼
